#ifndef MERGESORT_H
#define MERGESORT_H

#include "sortbase.h"
#include <QEventLoop>
#include <QVariantAnimation>

class MergeSort : public SortBase
{
    Q_OBJECT
public:
    explicit MergeSort(QObject *parent = nullptr);

    // virtual function/interface for sort
    void sort(size_t num_of_elem, int interval) override;
    void stop() override;
    void draw(QPainter *painter, int width, int height) override;
    void skip() override;

private:
    void MSort(int front, int end);
    void merge(int front, int mid, int end);
    void wait(int ms);

private:
    QEventLoop loop;
    QVariantAnimation animation;
    std::vector<size_t> subArray_left, subArray_right;
    int interval{1};

    int curr_low{0}, curr_mid{0}, curr_high{0}, curr_offset{0};

    // formula for absolute index:
    // subArray_left_index = curr_low + (idx_left - 1)
    // subArray_right_index = (curr_mid + 1) + (idx_right - 1) = curr_mid + idx_right;
    // minus 1 is because updateRequest is posted after idx gets increased.
    int idx_left{0}, idx_right{0};

    // 0 from left, 1 from right, -1 idle
    int min_from{-1};

    bool init_subArray{false};
};

#endif // MERGESORT_H
